package A一周刷爆LeetCode.A基础班.E链表;

import java.util.HashMap;

/**
 * @author wei.zhao
 * @description: 复制带有随机节点的链表
 * @date 2022年01月26日 10:18
 */
public class Code06_CopyListWithRandom {

    public static void main(String[] args) {
        Node head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(3);
        head.next.next.next = new Node(4);
        head.next.next.next.next = new Node(5);
        head.next.next.next.next.next = new Node(6);

        head.rand = head.next.next.next.next.next; // 1 -> 6
        head.next.rand = head.next.next.next.next.next; // 2 -> 6
        head.next.next.rand = head.next.next.next.next; // 3 -> 5
        head.next.next.next.rand = head.next.next; // 4 -> 3
        head.next.next.next.next.rand = null; // 5 -> null
        head.next.next.next.next.next.rand = head.next.next.next; // 6 -> 4

        printRandLinkedList(head);
        System.out.println("===========方法一==========");
        Node copy01 = copyListWithRand01(head);
        printRandLinkedList(copy01);
        System.out.println("===========方法二==========");
        Node copy02 = copyListWithRand02(head);
        printRandLinkedList(copy02);
        System.out.println("===========方法三==========");
        Node copy03 = copyListWithRand03(head);
        printRandLinkedList(copy03);
    }

    //带有随机节点的节点
    public static class Node {
        public int value;
        public Node next;
        public Node rand;

        public Node(int data) {
            this.value = data;
        }
    }

    //借助额外数据结构HashMap
    public static Node copyListWithRand01(Node head) {
        HashMap<Node, Node> map = new HashMap<>();
        //复制节点，用map维护原节点与复制的节点关系
        Node cur = head;
        while (null != cur) {
            map.put(cur, new Node(cur.value));
            cur = cur.next;
        }
        //设置节点关系
        cur = head;
        while (null != cur) {
            Node node = map.get(cur);
            Node next = map.get(cur.next);
            Node rand = map.get(cur.rand);
            node.next = next;
            node.rand = rand;
            cur = cur.next;
        }
        return map.get(head);
    }

    //使用有限几个变量
    public static Node copyListWithRand02(Node head) {
        //计算节点个数
        int i = 0;
        Node cur = head;
        while (null != cur) {
            i++;
            cur = cur.next;
        }
        //将原链表节点放入数组中，并将下一个节点指向复制的节点；生成复制的链表。
        Node[] nodes = new Node[i];
        i = 0;
        cur = head;
        Node copyCur = null;
        while (null != cur) {
            //当前节点放入数组
            nodes[i] = cur;
            i++;
            Node next = cur.next;
            Node copyNode = new Node(cur.value);
            if (null == copyCur) {
                copyCur = copyNode;
            } else {
                copyCur.next = copyNode;
                copyCur = copyNode;
            }
            cur.next = copyNode;
            cur = next;
        }
        //复制的头节点
        Node result = nodes[0].next;
        //遍历数组搞定复制链表的随机节点
        for (i = 0; i < nodes.length; i++) {
            Node node = nodes[i];
            Node rand = node.rand;
            if (null != rand) {
                Node curNext = node.next;
                Node randNext = rand.next;
                curNext.rand = randNext;
            }
        }
        //还原链表；
        for (i = 0; i < nodes.length; i++) {
            nodes[i].next = i == nodes.length - 1 ? null : nodes[i + 1];
        }
        return result;
    }

    //使用有限几个变量
    public static Node copyListWithRand03(Node head) {
        Node cur = head;
        //复制节点，当前节点指向复制节点，复制节点指向原节点的下一个节点
        while (null != cur) {
            Node next = cur.next;
            Node copyNode = new Node(cur.value);
            cur.next = copyNode;
            copyNode.next = next;
            cur = next;
        }
        //为复制节点指定随机节点
        cur = head;
        while (cur != null) {
            Node rand = cur.rand;
            Node next = cur.next;
            if (null != rand) {
                next.rand = rand.next;
            }
            cur = next.next;
        }
        //将链表拆分成两个
        cur = head;
        Node result = head.next;
        Node copyCur = result;
        while (cur != null) {
            Node next = copyCur.next;
            Node copyNext = next == null ? null : next.next;
            cur.next = next;
            copyCur.next = copyNext;
            cur = next;
            copyCur = copyNext;
        }
        return result;
    }

    //打印带有随机节点的链表
    public static void printRandLinkedList(Node head) {
        Node cur = head;
        System.out.print("order: ");
        while (cur != null) {
            System.out.print(cur.value + " ");
            cur = cur.next;
        }
        System.out.println();
        cur = head;
        System.out.print("rand:  ");
        while (cur != null) {
            System.out.print(cur.rand == null ? "- " : cur.rand.value + " ");
            cur = cur.next;
        }
        System.out.println();
    }

}
